package com.leecode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * 17. 电话号码的字母组合
 * 给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。
 * 给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
 * 示例:
 * 输入："23"
 * 输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
 */
public class Leet17 {
	public static void main(String[] args) {
//		new Leet17().letterCombinations("2");
		new Leet17().letterCombinations("23");
	}

	String[] mapping = new String[]{"0", "1", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz" };

	public List<String> letterCombinations(String digits) {
		List<String> list = new ArrayList<>();
		if(digits.equals("")) return list;
		// 数字对应的字符
		String[] strs = new String[]{"abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
		// 准备临时字节数组chars
		int len = digits.length();
		char[] chars = new char[len];
		// 递归，从第0个数字开始
		recurse(strs, list, digits, chars, 0);
		return list;
	}
	public void recurse(String[] strs, List<String> list, String digits, char[] chars, int count){
		// 处理完所有数字后，将chars对应的字符串加入到list中
		if(count == chars.length){
			list.add(new String(chars));
			return;
		}
		// 遍历第count个数字对应的每个字母
		for(char c: strs[digits.charAt(count)-'2'].toCharArray()){
			// 放到chars中的第count个位置上
			chars[count] = c;
			// 递归处理第(count+1)个数字
			recurse(strs, list, digits, chars, count + 1);
		}
	}

	/**
	 * backTrace,33%,36%,注意String经过recur不会改变
	 */
	public List<String> letterCombinations2(String digits) {
		List<String> res=new ArrayList();
		if(digits==null || digits.length()==0)return res;

		backTrace(res,digits,0,0,"");
		return res;
	}
	public void backTrace(List<String> res,String digits,int index,int n,String temp){
		if(n==digits.length()){
			res.add(temp);
			return;
		}
		int mapIndex=digits.charAt(index)-'0';//bug:char直接转int有点大..
		String str=mapping[mapIndex];

		for(int a=0;a<str.length();a++){
			// temp+=str.charAt(a);//若改变temp,就一定要backTrace temp
			backTrace(res,digits,index+1,n+1,temp+str.charAt(a));
		}
	}

	/**
	 * 100%,97%,又出现了,StringBuilder经过recur会改变
	 */
	public List<String> letterCombinations3(String digits) {
		List<String> res=new ArrayList();
		if(digits==null || digits.length()==0)return res;

		backTrace(res,digits,0,0,new StringBuilder(""));
		return res;
	}
	public void backTrace(List<String> res,String digits,int index,int n,StringBuilder temp){
		if(n==digits.length()){
			res.add(temp.toString());
			return;
		}
		int mapIndex=digits.charAt(index)-'0';//bug
		String str=mapping[mapIndex];

		for(int a=0;a<str.length();a++){
			// temp+=str.charAt(a);//
			backTrace(res,digits,index+1,n+1,temp.append(str.charAt(a)));
			temp.deleteCharAt(temp.length()-1);
		}
	}
}
